package ranges;

object Ranges{

  val Shorts = new ConcreteRange(java.lang.Short.MIN_VALUE, java.lang.Short.MAX_VALUE);
  val Bytes = new ConcreteRange(java.lang.Byte.MIN_VALUE, java.lang.Byte.MAX_VALUE);

  implicit def toInteger(i : Range#Index) = i.toInt;
  implicit def inclusion[S <: Range#Index](index : Range#SubRange[S]#SubIndex) : S = index.asInstanceOf[S];

  def range(start : Int, end : Int) = new ConcreteRange(start, end);

  class ConcreteRange(start : Int, end : Int) extends Range(start, end){
    type T = Index;
    private[Ranges] def unsafeFromInt (i : Int) = Index(i);
  }

  abstract class Range(val start : Int, val end : Int){
    type T <: Index;

    if (start >= end) throw new IndexOutOfBoundsException();

    def checkRange(min : Int, max : Int){
      if (min < start || max > end) throw new IndexOutOfBoundsException();
    }

    def inBounds(x : Int) : Index = unsafeFromInt(Math.min(end - 1, Math.max(x, start)));
    def checkBounds (x : Int) : Index = if (x < start || x >= end) throw new IndexOutOfBoundsException() else unsafeFromInt(x);

    private[Ranges] def unsafeFromInt (i : Int) : T;

    val range = start until end;
    val length = end - start;

    val maxIndex = unsafeFromInt(end - 1);
    val minIndex = unsafeFromInt(start);
    val midIndex = minIndex.mid(maxIndex);
    val indices = range.map(unsafeFromInt(_));

    trait Slice[T] extends Iterable[T] {
      def apply(i : Index) : T = unsafeApply(i);     
      def update(i : Index, t : T) = unsafeUpdate(i, t);

      private[Ranges] def unsafeApply(i : Int) : T;
      private[Ranges] def unsafeUpdate(i : Int, t : T) : Unit;

      def elements = range.elements.map(unsafeApply(_)); 
    } 

    class ArraySlice[T](array : Array[T]) extends Slice[T]{
      if (length < end) throw new IndexOutOfBoundsException();
      private[Ranges] def unsafeApply(i : Int) = array(i);
      private[Ranges] def unsafeUpdate(i : Int, t : T) : Unit = array(i) = t;

      override def foreach(f : T => Unit) = for (val i <- range) array(i);
    }

    class CheckedArray[T] extends Slice[T]{
      private val array = new Array[T](length);
      
      private[Ranges] def unsafeApply(i : Int) = array(i - start);
      private[Ranges] def unsafeUpdate(i : Int, t : T) : Unit = array(i - start) = t;
      
      override def foreach(f : T => Unit) = array.foreach(f);
    }

    case class Index private[Ranges] (val toInt : Int) extends Ordered[Index]{
      def max(y : Index) = unsafeFromInt(Math.max(this, y));
      def min(y : Index) = unsafeFromInt(Math.min(this, y));
      def mid(y : Index) = unsafeFromInt((this + y) >>> 1);
      def opposite = unsafeFromInt(end + start - 1 - this);
      def compare(that : Index) = this.toInt.compare(that);
    }; 

    // Subrange operations
    def from(i : Index) = new SubRange[Index](i, end);
    def upTo(i : Index) = new SubRange[Index](start, i);
    def split : Option[(SubRange[Index], SubRange[Index])] = 
      if (length == 1) None 
      else Some(new SubRange[Index](start, midIndex + 1), new SubRange[Index](midIndex + 1, end))

    class SubRange[T <: Range#Index](start : Int, end : Int) extends Range(start, end){
      type T = SubIndex;
      def unsafeFromInt(i : Int) = new SubIndex(i);
      
      class SubIndex private[Ranges](i : Int) extends Index(i);
    }
  }
}
